////////////////////////////////////////////////////////////////////////////////
// Auteur	: Maxime Vanier et Patrick Losier
// date		: 04/03/2013
//
// description : Declaration des differents algorithmes
///////////////////////////////////////////////////////////////////////////////
#ifndef _ALGORITHMES_H_
#define _ALGORITHMES_H_

#include <map>
#include <vector>
#include <set>
#include <string>
#include "Timer.h"


class BTS;

class Algo
{
public:
	// Constructeur/Destructeur
	Algo(std::string ID) : ID_(ID), time_(0), valeurMax_(0) {};
	~Algo() {};

	virtual int execute(const std::map<int, BTS*>& vBTS, int capacite, std::vector<int>& result) = 0;

	std::string getID() { return ID_; }

	void setTimeout(double delay) { timeout_ = delay; }

	int getSolution() { return valeurMax_; }

protected:
	double time_;
	double timeout_;

	int valeurMax_;

private:
	std::string ID_;
	
};

class AlgoVorace : public Algo
{
public:
	// Constructeur/Destructeur
	AlgoVorace(bool probabilist = true);
	~AlgoVorace();

	static const std::string ID_VORACE;

	// Methode a surcharger de l<interface Algo
	virtual int execute(const std::map<int, BTS*>& vBTS, int capacite, std::vector<int>& result);

protected:
	int executeIteration(const std::map<int, BTS*>& vBTS, int capacite, std::vector<int>& result);

	BTS* chooseBestLeft(const std::map<int, BTS*>& vBTS);

	bool probabilist_;


};

class AlgoDynamique : public Algo
{
public:
	// Constructeur/Destructeur
	AlgoDynamique();
	~AlgoDynamique();

	static const std::string ID_DYNAMIQUE;

	// Methode a surcharger de l'interface Algo
	virtual int execute(const std::map<int, BTS*>& vBTS, int capacite, std::vector<int>& result);

protected:

};

class AlgoBranchAndBound : public Algo
{
public:
	// Constructeur/Destructeur
	AlgoBranchAndBound();
	~AlgoBranchAndBound();

	static const std::string ID_BRANCH_AND_BOUND;

	// Methode a surcharger de l<interface Algo
	virtual int execute(const std::map<int, BTS*>& vBTS, int capacite, std::vector<int>& result);


protected:
	 
	void convertMap2MultiMap(const std::map<int, BTS*>& mBTS);

	int CalculNoeud(int capaciteRestante, int valeurCourante);

private:

	std::multimap<double, BTS*> mmBTS_;
	Timer timer_;
	std::multimap<double, BTS*> ::const_reverse_iterator position_;

};

#endif //_ALGORITHMES_H_